/**
 * 带权并查集
 * 
 * Feature:
 * 1. 小树向大树合并，保证平衡
 * 2. 扁平化，减少查询深度
 * 
 * @author shuyuan.dai 2021-02-04
 */
class UnionFind {
    constructor(size) {
        this.sz = [];
        this.parent = [];
        this.count = size;
        for (let i = 0; i < size; ++i) {
            this.parent[i] = i;
            this.sz[i] = 1;
        }
    }

    transferToQuickSearchMode() {
        for(let i=0; i < this.parent.length; ++i) {
            this.parent[i] = this.find(i);
        }
    }

    connected(x, y) {
        return this.find(x) == this.find(y);
    }

    union(x, y) {
        let i = this.find(x),
            j = this.find(y);

        if (i == j) return;

        if (this.sz[i] < this.sz[j]) {
            this.parent[i] = j;
            this.sz[j] += this.sz[i];
        } else {
            this.parent[j] = i;
            this.sz[i] += this.sz[j];
        }

        this.count--;
    }

    find(u) {
        while (u != this.parent[u]) u = this.parent[u];
        return u;
    }
}

exports.UnionFind = UnionFind;